package com.atguigu.day01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @description :
 * @autor :lyh
 */
public class Example3 {
    public static void main(String[] args) {
        // key 顶点的名字
        // value 顶点指向的所有顶点组成的列表
        HashMap<String, List<String>> dag = new HashMap<>();

        ArrayList<String> ANeighbor = new ArrayList<>();
        ANeighbor.add("B");
        ANeighbor.add("C");
        dag.put("A", ANeighbor);

        ArrayList<String> BNeighbor = new ArrayList<>();
        BNeighbor.add("D");
        BNeighbor.add("E");
        dag.put("B", BNeighbor);

        ArrayList<String> CNeighbor = new ArrayList<>();
        CNeighbor.add("D");
        CNeighbor.add("E");
        dag.put("C", CNeighbor);

        // 找出从顶点到终点的所有路径
        // 拓扑排序
        topologicalSort(dag, "A", "A");

    }

    /**
     * @param dag
     * @param vertex
     * @param path
     */
    public static void topologicalSort(HashMap<String, List<String>> dag, String vertex, String path) {
        if (vertex.equals("D") || vertex.equals("E")) {
            System.out.println(path);
        } else {
            for (String neighbor : dag.get(vertex)) {
                topologicalSort(dag, neighbor, path + "=>" + neighbor);
            }
        }
    }
}
